package binarytree

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
// 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
// 本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。
// 分割点就是数组中间位置的节点。
func sortedArrayToBST(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	} //终止条件，最后数组为空则可以返回
	root := &TreeNode{nums[len(nums)/2], nil, nil}      //按照BST的特点，从中间构造节点
	root.Left = sortedArrayToBST(nums[:len(nums)/2])    //数组的左边为左子树
	root.Right = sortedArrayToBST(nums[len(nums)/2+1:]) //数字的右边为右子树
	return root
}
